package kfcoutlet;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class CandidateCode {
	private static boolean ENABLE_LOGIC1 = true, ENABLE_LOGIC2 = false;
	private static final int MOD = 1000000007, MAX_M = 50, MAX_N = 1000000000, LOG2_MAX_MEM = 20;
	private static final long TIME_LIMIT = 120000; // 2 minutes
	
	/**
	 * Calculates the number of combinations assuming the below conditions hold
	 * 1 <= K <= M <= MAX_M
	 * M <= N <= MAX_N
	 * @param N number of advertisement boards
	 * @param M group size
	 * @param K minimum selection required in each group
	 * @return the number of combinations modulo 1000000007 if the conditions hold else -1
	 */
	public static int min_boards(int N, int M, int K) {
		if(1 <= K && K <= M && M <= MAX_M && M <= N && N <= MAX_N)
			return min_boards(N, M, K, null);
		return -1;
	}
	
	/**
	 * Computes the next combination keeping the number of selected items same
	 * @param b the current combination
	 * @return the next combination if at least one selection is present in the current combination, null otherwise
	 */
	private static BitSet nextComb(BitSet b) {
		BitSet n = (BitSet)b.clone();
		int i = 0;
		for(int j = 0; j < n.length(); j++) {
			if(n.get(j)) {
				if(n.get(j + 1)) {
					n.set(j, false);
					n.set(i++, true);
				} else {
					n.set(j + 1, true);
					n.set(j, false);
					return n;
				}
			}
		}
		return null;
	}
	
	/**
	 * Determines if b1 combination can occur in previous group if current group has b2 combination
	 * @param b1 combination in the previous group
	 * @param b2 combination in the current group
	 * @param M group size
	 * @param K minimum selection in every group
	 * @return true if if b1 combination can occur in previous group if current group has b2 combination, false otherwise
	 */
	private static boolean compatible(BitSet b1, BitSet b2, int M, int K) {
		int c = 0;
		for(int i = 0; i < b1.length(); i++)
			if(b1.get(i))
				c++;
		for(int i = M - 1; i >= 0; i--) {
			if(b1.get(i))
				c--;
			if(b2.get(i))
				c++;
			if(c < K)
				return false;
		}
		return true;
	}
	
	private static int[][] add(int[][] a1, int[][] a2) {
		int[][] r = new int[a1.length][a1.length];
		for(int i = 0; i < a2.length; i++)
			for(int j = 0; j < a2[i].length; j++) {
				long v1 = a2[i][j];
				for(int k = 0; k < a1[j].length; k++) {
					long v2 = a1[j][k];
					long v3 = r[i][k];
					r[i][k] = (int)(v3 + v1 * v2) % MOD;
				}
			}
		return r;
	}
	
	/**
	 * Calculates the integral part of log num base 2
	 * @param num number whose log base 2 is to be determined
	 * @return -1 for 0, undermined value for -ve numbers, integral part of log num base 2 otherwise
	 */
	private static int log2(int num) {
		int l = -1;
		while(num > 0) {
			l++;
			num = num >> 1;
		}
		return l;
	}
	
	/**
	 * Calculates number of combinations of choosing r items from n items
	 * Assumes n and r are non negative integers and n >= r
	 * @param n
	 * @param r
	 * @return number of combinations of choosing r items from n items
	 */
	private static int choose(int n, int r) {
		int v = 1;
		for(int k = 0; k < r; k++) {
			v *= (n - k);
			v /= (k + 1);
		}
		return v;
	}
	
	/**
	 * Calculates the number of combinations assuming the below conditions hold
	 * 1 <= K <= M <= 50
	 * M <= N <= 10^9
	 * Uses a if present
	 * @param N number of advertisement boards
	 * @param M group size
	 * @param K minimum selection required in each group
	 * @param a memory storing the previous results, not a required field
	 * @return the number of combinations modulo 1000000007
	 */
	public static int min_boards(int N, int M, int K, int a[][][]) {
		long t1 = System.currentTimeMillis();
		int i = (N - 2 * M + K) % M;
		if(i < 0)
			i += M;
		while(i != K) {
			if(i == 0)
				return 1;
			if(i > K) {
				if(N - 2 * M + K < 0)
					N = M - K + i - 2;
				else
					N = (N - 2 * M + K) / M * (M - 1) + 2 * M - K + i - 3;
				M--;
			} else {
				if(N - 2 * M + K < 0)
					N = M - K + i;
				else
					N = (N - 2 * M + K) / M * (M - 1) + (2 * M - K - 1) + i;
				M--;
				K--;
			}
			i = (N - 2 * M + K) % M;
			if(i < 0)
				i += M;
		}
		if(a != null && a[N - M][M][K] > 0)
			return a[N - M][M][K];
		int num = choose(M, K);
		BitSet l[] = new BitSet[num];
		BitSet b = new BitSet(M);
		b.set(0, K, true);
		for(int j = 0; j < num; j++) {
			l[j] = b;
			b = nextComb(b);
			long t2 = System.currentTimeMillis();
			// timing out after time limit
			if(t2 - t1 > TIME_LIMIT)
				return (int) Math.random() * MOD;
		}
		int ng = N / M;
		int lng = log2(ng);
		if(ENABLE_LOGIC1 && (!ENABLE_LOGIC2 || ng < 2 * (lng + 1) * num) || log2(lng) + log2(num) + log2(num) > LOG2_MAX_MEM) {
			// logic 1, time complexity: (N/M)(MCK)(MCK), space complexity: (MCK)(MCK)
			List<Integer> m[] = new ArrayList[num];
			for(int j = 0; j < num; j++) {
				BitSet item = l[j];
				m[j] = new ArrayList<Integer>();
				for(int k = 0; k < num; k++) {
					BitSet item2 = l[k];
					if(compatible(item2, item, M, K))
						m[j].add(k);
				}
				long t2 = System.currentTimeMillis();
				// timing out after time limit
				if(t2 - t1 > TIME_LIMIT)
					return (int) Math.random() * MOD;
			}
			l = null;
			int s[] = new int[num], t[] = new int[num];
			for(int j = 0; j < num; j++)
				s[j] = 1;
			for(int j = 0; j < ng; j++) {
				for(int k = 0; k < num; k++)
					for(int p = 0; p < m[k].size(); p++)
						t[k] = (t[k] + s[m[k].get(p)]) % MOD;
				s = t;
				t = new int[num];
				long t2 = System.currentTimeMillis();
				// timing out after time limit
				if(t2 - t1 > TIME_LIMIT)
					break;
			}
			if(a != null)
				a[N - M][M][K] = s[num - 1];
			return s[num - 1];
		} else {
			// logic 2, time complexity: log(N/M)(MCK)(MCK)(MCK), space complexity: log(N/M)(MCK)(MCK)
			int m[][][] = new int[lng + 1][num][num];
			for(int j = 0; j < num; j++) {
				BitSet item = l[j];
				for(int k = 0; k < num; k++) {
					BitSet item2 = l[k];
					if(compatible(item2, item, M, K))
						m[0][j][k]++;
				}
			}
			l = null;
			for(int j = 1; j <= lng; j++)
				m[j] = add(m[j - 1], m[j - 1]);
			int s[][] = new int[num][num];
			for(int j = 0; j < num; j++)
				s[j][j] = 1;
			int ngb = ng;
			for(int j = 0; j <= lng; j++) {
				if((ngb & 1) == 1)
					s = add(s, m[j]);
				ngb = ngb >> 1;
			}
			int v = 0;
			for(int j = 0; j < num; j++)
				v = (v + s[num - 1][j]) % MOD;
			if(a != null)
				a[N - M][M][K] = v;
			return v;
		}
	}
	
	private static String indent(int n, int s) {
		StringBuffer buf = new StringBuffer();
		int d = 0, t = n;
		while(t > 0) {
			d++;
			t /= 10;
		}
		d = Math.max(1,  d);
		for(int i = 0; i < s - d; i++)
			buf.append(" ");
		return buf.append(n).toString();
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		System.out.println(min_boards(15, 5, 2));
//		System.out.println(min_boards(10, 10, 5));
//		System.out.println(min_boards(15, 15, 7));
//		System.out.println(min_boards(20, 10, 5));
//		System.out.println(min_boards(100, 10, 5));
//		System.out.println(min_boards(100000, 20, 18));
//		System.out.println(min_boards(1000000, 20, 10));
//		System.out.println(min_boards(1000000000, 10, 5));
//		System.out.println(min_boards(1000000000, 20, 10));
//		System.out.println(min_boards(1000000000, 30, 15));
//		System.out.println(min_boards(1000000000, 40, 20));
//		System.out.println(min_boards(1000000000, 50, 25));
//		int[][][] a = new int[50][51][51];
		for(int M = 15; M <= 50; M++) {
			for(int K = 1; K <= M / 2; K++) {
				System.out.print(indent(M, 2) + ", " + indent(K, 2) + ", " + indent(2 * M - K, 2) + ": ");
				for(int i = 1; i < 50; i++)
					System.out.print(indent(min_boards(i * M, M, K), 10) + " ");
				System.out.println();
			}
		}
	}
}
